class Node(object):
    """节点"""
    def __init__(self, item):
        self.item = item            # 节点内容
        self.son:list[Node]|None = None  # 树的子节点可以有多个
        self.dad:Node|None = None        # 树的父节点只能有一个


class Tree(object):
    """树结构"""
    def __init__(self, root:Node|None=None):
        self.root:Node|None = root

    def isempty(self):
        return self.root is None

    def add(self, node:Node, dad:Node|None=None):
        if dad is None:                 # 没有指定父节点，node节点即为根节点的子节点
            if self.root is None:           # 根节点不存在
                self.root = node                # node就是根节点
            else:                           # 根节点存在
                node.dad = self.root            # node的父节点就是根节点
        else:                           # 指定了父节点
            node.dad = dad
            try:
                dad.son.append(node)
            except:
                dad.son = [node]

    def remmove(self, node:Node):
        """删除此节点以及此节点的所有子节点"""
        node.dad.son.remove(node)
        node.dad = None

    def dfs(self, node, path):
        """深度优先遍历"""
        if node is None:
            return
        path.append(node.item)  # 将当前节点添加到路径中
        if node.son is None:  # 如果当前节点是叶子节点
            self.paths.append(path.copy())  # 将路径添加到路径列表中
        else:
            for son in node.son:  # 遍历子节点
                self.dfs(son, path)
        path.pop()  # 从路径中移除当前节点

    def get_all_paths(self):
        """获取从根节点到所有叶子节点的所有路径"""
        self.paths = []
        self.dfs(self.root, [])
        return self.paths


if __name__ == '__main__':
    tree = Tree()
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3)
    node4 = Node(4)
    node5 = Node(5)
    node6 = Node(6)
    tree.add(node1)
    tree.add(node2, node1)
    tree.add(node3, node1)
    tree.add(node4, node2)
    tree.add(node5, node2)
    tree.add(node6, node3)

    lst = tree.get_all_paths()
    
